package org.example.struct.array2;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author liyishan
 * @date 2023/9/28 10:24
 * @apiNote
 */

public class Test00128LongestConsecutive {
    /**
     * 方法一：先排序  然后去重   然后找连接的最长子序列
     * @param nums
     * @return
     */
    public int test1(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        Arrays.sort(nums);
        removeDuplicates(nums);
        int max = 1;
        int start = 0;
        for(int i = 1;i < n;i++){
            if(nums[i] <= nums[i - 1] || nums[i] - nums[i-1] > 1){
                start = i;
            }
            max = Math.max(max,i - start + 1);
        }
        return max;
    }

    public static int removeDuplicates(int[] nums) {
        int slow = 1;
        int fast = 1;
        while(fast < nums.length){
            if(nums[fast] != nums[fast-1]){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }


    /**
     * 方法二：hash
     * @param nums
     * @return
     */
    public int test2(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) {
            numSet.add(num);
        }
        int longestStreak = 0;
        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;

    }

}
